package Leetcode.DayTest;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: kirito
 * @Date: 2024/5/20 17:27
 * @Description:
 * 找出最长的超赞子字符串
 * 困难
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
 *
 * 「超赞子字符串」需满足满足下述两个条件：
 *
 * 该字符串是 s 的一个非空子字符串
 * 进行任意次数的字符交换后，该字符串可以变成一个回文字符串
 *
 *
 * 示例 1：
 *
 * 输入：s = "3242415"
 * 输出：5
 * 解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"
 * 示例 2：
 *
 * 输入：s = "12345678"
 * 输出：1
 * 示例 3：
 *
 * 输入：s = "213123"
 * 输出：6
 * 解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"
 * 示例 4：
 *
 * 输入：s = "00"
 * 输出：2
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 10^5
 * s 仅由数字组成
 */

public class longestAwesome {
    /**
     *
     * @param s
     * @return
     */
    public int longestAwesome(String s) {
        int n = s.length(); // 获取字符串的长度
        Map<Integer, Integer> prefix = new HashMap<Integer, Integer>(); // 创建一个HashMap来记录每个sequence第一次出现的位置
        prefix.put(0, -1); // 初始化，当sequence为0时，代表没有任何字符出现过，标记为-1
        int ans = 0; // 初始化最长序列的长度为0
        int sequence = 0; // 初始化sequence，代表当前字符之前的字符序列的状态
        for (int j = 0; j < n; ++j) { // 遍历字符串
            int digit = s.charAt(j) - '0'; // 获取当前字符（数字）的十位数字
            sequence ^= (1 << digit); // 更新sequence，通过异或操作去掉sequence中对应digit的位
            if (prefix.containsKey(sequence)) { // 如果HashMap中存在当前sequence，说明当前字符之前的序列之前出现过
                ans = Math.max(ans, j - prefix.get(sequence)); // 更新最长序列的长度
            } else { // 如果当前sequence是第一次出现
                prefix.put(sequence, j); // 在HashMap中记录sequence和对应的位置
            }
            for (int k = 0; k < 10; ++k) { // 遍历所有可能的数字（0-9）
                if (prefix.containsKey(sequence ^ (1 << k))) { // 检查去掉当前digit后的新sequence是否出现过
                    ans = Math.max(ans, j - prefix.get(sequence ^ (1 << k))); // 如果是，更新最长序列的长度
                }
            }
        }
        return ans; // 返回最长序列的长度
    }


}
